package leetcode.bfs;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author : zx
 * @version V1.0
 */
public class medium_序列化和反序列化二叉搜索树 {


    public class Codec {

        public class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null){
                return "null";
            }
            StringBuilder sb = new StringBuilder();
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);
            sb.append(root.val+",");
            while (!q.isEmpty()){
                TreeNode tmp = q.poll();
                if (tmp.right != null){ q.offer(tmp.right); sb.append(tmp.right.val+","); }
                else { sb.append("null,"); }
                if (tmp.left != null) { q.offer(tmp.left); sb.append(tmp.left.val+","); }
                else { sb.append("null,"); }
            }
            return sb.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.equals("null")) return null;
            String[] arrs = data.split(",");
            int i = 0;
            Queue<TreeNode> q = new LinkedList<>();
            TreeNode head = new TreeNode(Integer.valueOf(arrs[i++]));
            q.offer(head);
            for (; i < arrs.length && !q.isEmpty(); i+=2){
                TreeNode tmp = q.poll();
                if (!arrs[i].equals("null")){
                    TreeNode right = new TreeNode(Integer.valueOf(arrs[i]));
                    tmp.right = right;
                    q.offer(right);
                }
                if (!arrs[i+1].equals("null")){
                    TreeNode left = new TreeNode(Integer.valueOf(arrs[i+1]));
                    tmp.left = left;
                    q.offer(left);
                }
            }
            return head;
        }
    }
}
